import java.util.NoSuchElementException;

/**
 * 双链表实现
 */
public class DoublyLinkedList<E> {

    // 虚拟头尾节点
    private Node<E> head, tail;
    private int size;

    private static class Node<E> {
        E val;
        Node<E> prev, next;

        Node(E val) {
            this.val = val;
        }
    }

    // 构造函数初始化虚拟头尾节点
    public DoublyLinkedList() {
        this.head = new Node<>(null);
        this.tail = new Node<>(null);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
    }

    public void addLast(E e) {
        Node<E> node = new Node<>(e);
        Node<E> temp = tail.prev;
        // temp <-> node;
        temp.next = node;
        node.prev = temp;
        // temp <-> node <-> tail;
        node.next = tail;
        tail.prev = node;
        size++;
    }

    public void addFirst(E e) {
        Node<E> node = new Node<>(e);
        Node<E> temp = head.next;
        // head <-> temp
        temp.prev = node;
        node.next = temp;
        // head <-> node <-> temp
        head.next = node;
        node.prev = head;
        size++;
    }

    public void add(int index, E e) {
        checkPositionIndex(index);
        if (index == size) {
            addLast(e);
            return;
        }
        // 找到index对应的node
        Node<E> node = getNode(index);
        Node<E> temp = node.prev;
        // temp <-> node
        // 新要插入的node
        Node<E> x = new Node<>(e);

        node.prev = x;
        temp.next = x;

        x.prev = temp;
        x.next = node;
        // temp <-> x <-> node
        size++;
    }

    public E removeFirst() {
        if (size < 1) {
            throw new NoSuchElementException();
        }
        // 虚拟节点的存在是我们不需要考虑控制针的问题
        Node<E> x = head.next;
        Node<E> temp = x.next;
        // head <-> x <-> node
        head.next = temp;
        temp.prev = head;

        E val = x.val;
        x.prev = null;
        x.next = null;
        // head <-> node
        size--;
        return val;
    }

    public E removeLast() {
        if (size < 1) {
            throw new NoSuchElementException();
        }
        Node<E> x = tail.prev;
        Node<E> temp = x.prev;
        // tepm <-> x <-> tail
        tail.prev = temp;
        temp.next = tail;
        E val = x.val;
        // temp <-> node
        x.prev = null;
        x.next = null;
        size--;
        return val;
    }

    public E remove(int index) {
        checkElementIndex(index);
        // 找到index对应的node
        Node<E> x = getNode(index);
        Node<E> prev = x.prev;
        Node<E> next = x.next;
        // prev <-> x <-> next
        prev.next = next;
        next.prev = prev;
        E val = x.val;
        x.prev = null;
        x.next = null;
        size--;
        return val;
    }

    public E get(int index) {
        checkElementIndex(index);
        Node<E> node = getNode(index);
        return node.val;
    }

    public E getFirst() {
        if (size < 1) {
            throw new NoSuchElementException();
        }
        return head.next.val;
    }

    public E getLast() {
        if (size < 1) {
            throw new NoSuchElementException();
        }
        return tail.prev.val;
    }

    public E set(int index, E e) {
        checkElementIndex(index);
        Node<E> node = getNode(index);
        E val = node.val;
        node.val = e;
        return val;
    }
    // 工具方法
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public Node<E> getNode(int index) {
        checkElementIndex(index);
        Node<E> p = head.next;
        // TODO: 可以优化，通过index判断从head开始遍历还是tail开始遍历
        for (int i = 0 ; i < index; i++) {
            p = p.next;
        }
        return p;
    }

    public boolean isElemenetIndex(int index) {
        return index >= 0 && index < size;
    }

    public boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    public void checkElementIndex(int index) {
        if (!isElemenetIndex(index))
            throw new IndexOutOfBoundsException("index: " + index + " size: " + size);
    }

    public void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException("index: " + index + " size: " + size);
    }

    public void display() {
        System.out.println("size =" + size);
        for (Node<E> p = head.next; p != tail; p = p.next) {
            System.out.print(p.val + "<->");
        }
        System.out.println("null");
        System.out.println();
    }
    public static void main(String[] args) {

    }
}
